/* 计算二叉树中所有叶子节点的个数 */

#include <iostream>
#include "BiTreefun.h"
using namespace std;

// 计算叶子结点个数 -- 方法一
int count(BTNode *p)
{
  int n1, n2;
  
  // 如果二叉树为空
  if (p == NULL)
    return 0;
  
  // 如果二叉树没有孩子 -- 叶子结点为1
  else if (p->lchild == NULL && p->rchild == NULL)
    return 1;
  
  // 有孩子
  else
  {
    // 统计左子树的叶子结点
    n1 = count(p->lchild);
    
    // 统计右子树的叶子结点
    n2 = count(p->rchild);
    
    // 返回
    return n1 + n2;
  }
}

// 计算叶子结点个数 -- 方法二
void count2(BTNode *p, int &n)
{
  // 如果不为空
  if (p != NULL)
  {
    // 是叶子结点
    if (p->lchild == NULL && p->rchild == NULL)
      ++n;
    
    // 统计左子树的叶子结点
    count2(p->lchild, n);
    
    // 统计右子树的叶子结点
    count2(p->rchild, n);
  }
}

int main()
{
  // 创建二叉树
  BTNode *T = create_bitree();
  
  // 计算叶子结点个数
  int n = count(T);
  
  // 打印
  cout << "二叉树中的叶子结点个数为:" << n << endl;
}